package fifsix_exp;

import java.util.Scanner;

public class RedBlackTreeTest {
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);

        RBTree<Integer, Object> rbt = new RBTree<Integer, Object>();

        // 插入值0-99
        for(int i = 0; i < 100; i++){
            rbt.insert(i, null);
        }

//        while(true){
//            System.out.println("请输入key: ");
//            String key = sc.next();
//            System.out.println();
//            rbt.insert(key, null);
//        }

        // rbt.inOrderPrint();
        if(rbt.IsValidRBTree())
            System.out.println("红黑树为有效红黑树！");
        else System.out.println("红黑树非法，生成失败");
    }

}
class RBTree<K extends Comparable<K>, V>
{
    // 根据红黑树规则判断是否为有效红黑树
    // 主要逻辑: 通过判断
    // ①二叉树每条路径上黑色结点是否都相等
    // ②红结点的子结点均为黑色结点
    // 这两个条件来断定是否为有效红黑树
    public boolean IsValidRBTree()
    {
        // 空树也为红黑树
        if(root == null)
            return true;
        RBNode x = root;
        int digitBlack = 0;
        while(x != null){
            if(x.color == BLACK){
                digitBlack++;
            }
            x = x.left;
        }
        return IsValidRBTree(root, digitBlack, 0);
    }

    private boolean IsValidRBTree(RBNode root, int blackCount, int pathBlack)
    {
        if(root == null){
            // 判断每条路径上的黑结点树是否都相同
            if(blackCount == pathBlack) {
                return true;
            }
            else{
                return false;
            }
        }
        // 判断红结点的parent结点是否都为黑结点
        if(root.color == RED && root.parent.color == RED) {
            return false;
        }

        // 递归的同时进行路径计数
        if(root.color == BLACK){
            return IsValidRBTree(root.left, blackCount, pathBlack + 1)
                    && IsValidRBTree(root.right, blackCount, pathBlack + 1);
        }
        else {
            return IsValidRBTree(root.left, blackCount, pathBlack)
                    && IsValidRBTree(root.right, blackCount, pathBlack);
        }
    }

    private static final boolean RED = true;
    private static final boolean BLACK = false;

    /**树根*/
    private RBNode root;


    /**
     * 获取当前结点的父节点
     * @param node
     */
    private RBNode parentOf(RBNode node)
    {
        if(node != null)
        {
            return node.parent;
        }
        return null;
    }

    /**
     * 结点是否为红色或黑色
     * @param node
     */
    private boolean isRed(RBNode node)
    {
        if(node != null)
        {
            return node.color == RED;
        }
        return false;
    }
    private boolean isBlack(RBNode node)
    {
        if(node != null)
        {
            return node.color == BLACK;
        }
        return false;
    }

    /**
     * 设置结点为红色或黑色
     * @param node
     */
    private void setRed(RBNode node)
    {
        if(node != null)
        {
            node.color = RED;
        }
    }
    private void setBlack(RBNode node)
    {
        if(node != null)
        {
            node.color = BLACK;
        }
    }

    /**
     * 中序打印二叉树
     */
    public void inOrderPrint()
    {
        inOrderPrint(this.root);
    }
    private void inOrderPrint(RBNode root)
    {
        if(root != null)
        {
            inOrderPrint(root.left);
            System.out.println("key:" + root.key + ", value:" + root.value);
            inOrderPrint(root.right);
        }
    }

    /**
     * 插入方法
     * @param key
     * @param value
     */
    public void insert(K key, V value)
    {
        RBNode node = new RBNode();
        node.key = key;
        node.value = value;
        // 新结点一定先为红色
        node.color = RED;
        insert(node);
    }
    private void insert(RBNode node)
    {
        // 查找当前node的父结点
        RBNode parent = null;
        RBNode x = this.root;

        while(x != null)
        {
            parent = x;
            // cmp大于0说明node.key大于x.key 需要到x的右子树查找
            //    等于            等于          进行替换操作
            //    小于            小于              左子树查找
            int cmp = node.key.compareTo(x.key);
            if(cmp > 0)
            {
                x = x.right;
            }
            else if(cmp < 0)
            {
                x = x.left;
            }
            else {
                x.value = node.value;
                return;
            }
        }
        node.parent = parent;
        if(parent != null) {
            int cmp = node.key.compareTo(parent.key);
            if (cmp > 0) { // 当前node大于parent，把node放入parent右子结点
                parent.right = node;
            } else { // 反之
                parent.left = node;
            }
        }
        else {
            this.root = node;
        }

        // 调用修复红黑树方法
        insertFixUp(node);
    }

    /**
     * 修复红黑树方法（维持平衡）
     */
    private void insertFixUp(RBNode node)
    {
        this.root.color = BLACK;

        RBNode parent = parentOf(node);
        RBNode gparent = parentOf(parent);

        // 插入父结点为红色
        if(isRed(parent))
        {
            RBNode uncle = null;
            // 父结点为爷爷结点左子树
            if(parent == gparent.left) {
                uncle = gparent.right;
                if(isRed(uncle)) { // uncle存在且为红
                    // 将parent和uncle染黑，gparent染红
                    // 再以gparent为当前结点进行下一步处理
                    parent.color = BLACK;
                    uncle.color = BLACK;
                    gparent.color = RED;
                    insertFixUp(gparent);
                    return;
                }
                else { // uncle不存在或为黑
                    // ll: node为parent左子树，parent为gparent左子树
                    if(node == parent.left){
                        parent.color = BLACK;
                        gparent.color = RED;
                        rightRotate(gparent);
                        return;
                    }
                    // lr:node为parent右子树，parent为gparent左子树
                    else {
                        leftRotate(parent);
                        insertFixUp(parent);
                        return;
                    }
                }
            }
            // 父结点为爷爷右子树
            else {
                uncle = gparent.left;
                if(isRed(uncle)) { // uncle存在且为红
                    // 将parent和uncle染黑，gparent染红
                    // 再以gparent为当前结点进行下一步处理
                    parent.color = BLACK;
                    uncle.color = BLACK;
                    gparent.color = RED;
                    insertFixUp(gparent);
                    return;
                }
                else { // uncle不存在或为黑
                    if(node == parent.right){ // rr
                        parent.color = BLACK;
                        gparent.color = RED;
                        leftRotate(gparent);
                        return;
                    }
                    else { // rl
                        rightRotate(parent);
                        insertFixUp(parent);
                        return;
                    }
                }
            }
        }
    }

    /**
     * 左旋
     *       p                    p
     *       x                    y
     *   lx     y     --->    x     ry
     *        ly ry         lx ly
     */
    private void leftRotate(RBNode x)
    {
        RBNode y = x.right;
        // 将x的右子结点指向y的左子结点
        // 将y的左子结点的父节点更新为x
        x.right = y.left;
        if(y.left != null)
        {
            y.left.parent = x;
        }

        // x结点父结点（不为空时），更新为y的父结点
        // 并将x的父结点指定为y
        if(x.parent != null){
            y.parent = x.parent;
            if(x == x.parent.left)
            {
                x.parent.left = y;
            }
            else
            {
                x.parent.right = y;
            }
        }
        else // 说明x为根结点，需要更新y为根节点
        {
            this.root = y;
            this.root.parent = null;
        }

        // 将x的父结点更新为y，将y的左子节点更新为x
        x.parent = y;
        y.left = x;
    }

    /**
     * 右旋
     *       p               p
     *       y               x
     *    x    ry  --->   lx    y
     *  lx ly                 ly ry
     */
    private void rightRotate(RBNode y)
    {
        RBNode x = y.left;
        // 将y的左子结点指向x的右子结点
        // 将x的右子结点的父节点更新为y
        y.left = x.right;
        if(x.right != null)
        {
            x.right.parent = y;
        }

        // y结点父结点（不为空时），更新为x的父结点
        // 并将y的父结点指定为x
        if(y.parent != null){
            x.parent = y.parent;
            if(y == y.parent.right)
            {
                y.parent.right = x;
            }
            else
            {
                y.parent.left = x;
            }
        }
        else // 说明y为根结点，需要更新x为根节点
        {
            this.root = x;
            this.root.parent = null;
        }

        // 将y的父结点更新为x，将x的右子节点更新为y
        y.parent = x;
        x.right = y;
    }

    static class RBNode<K extends Comparable<K>, V>
    {
        public RBNode parent;
        public RBNode left;
        public RBNode right;

        public boolean color;
        public K key;
        public V value;

        public RBNode()
        {}

        public RBNode(RBNode parent, RBNode left, RBNode right, boolean color, K key, V value) {
            this.parent = parent;
            this.left = left;
            this.right = right;
            this.color = color;
            this.key = key;
            this.value = value;
        }

    }

}
